
/* Listar poi para turista */
lista_poi_turista(IDtur,L):- lista_f_turista(IDtur,LFtur), passar(LFtur,L).

lista_f_turista(IDtur,LFtur):- setof(f(F,IDpoi),avalia_poi_t(IDpoi,IDtur,F),L),reverse(L,LFtur).

avalia_poi_t(IDpoi,IDtur,F):- poi(IDpoi,_,Tipo,Cpoi),mod_turista(IDtur,_,L),member(c(Tipo,Nt),L),f_aval(Cpoi,Nt,F).

f_aval(Cpoi,Nt,F):-F is Cpoi + Nt.


passar([],[]):-!.
passar([f(_,X)|L],[X|L1]):-passar(L,L1).



/* Calcular distancias entre poi */
todas_distancias:-findall(_,(calc_distancia(P1,P2,D),assertz(distancia(P1,P2,D))),_).

calc_distancia(P1,P2,D):-
	coord_poi(P1,X1,Y1),
	coord_poi(P2,X2,Y2),
	P2>P1,
	DX is X1-X2,
	DY is Y1-Y2,
	D is sqrt(DX*DX+DY*DY).

:-todas_distancias.




/* tds_dist_sec:- findall(_,(atrib_dist(P1,P2,D), assertz(seccao(P1,P2,D))),_), findall(_,(retract(seccao(_,_,0))),_).

atrib_dist(P1,P2,D):- (distancia(P1,P2,D); distancia(P2,P1,D)), seccao(P1,P2,_).

:-tds_dist_sec. */


/* Melhor caminho */
melhor_caminho(Lpoi,Lpoim,D):-findall(Lpoip12,(permuta(Lpoi,Lpoip),append([-1|Lpoip],[-2],Lpoip12)),LLpoi),menor_caminho(LLpoi,Lpoim,D),write(Lpoim),write(' '), write(D).
 
menor_caminho([Lpoi],Lpoi,D):-!,calc_dist_total(Lpoi,D).
menor_caminho([Lpoi|LLpoi],Lpoim,D):-menor_caminho(LLpoi,Lpoim2,D2),calc_dist_total(Lpoi,D1),((D1<D2,!,Lpoim=Lpoi,D is D1);(Lpoim=Lpoim2,D is D2)).

calc_dist_total([_],0).
calc_dist_total([P1,P2|LP],D):-calc_dist_total([P2|LP],D2LP),((distancia(P1,P2,D12),!);distancia(P2,P1,D12)),D is D12+D2LP.

permuta([ ],[ ]).
permuta(L,[X|L1]):-elimina_(X,L,Li),permuta(Li,L1).

elimina_(X,[X|L],L).
elimina_(X,[Y|L],[Y|L1]):-elimina_(X,L,L1).fv
 


/* Caminho caixeiro viajante */
caminho_caixeiro_viajante(Lpoi,[-1|Lpoicv],D):-menor_distancia_membro_lista(-1,Lpoi,P,Lpoi1,D1),
							caminho_caixeiro_viajante1(P,Lpoi1,Lpoicv,Pf,Dpoi),
							(distancia(Pf,-2,D2);distancia(-2,Pf,D2)),
							D is D1+Dpoi+D2.


caminho_caixeiro_viajante1(P,[],[P,-2],P,0):-!.
caminho_caixeiro_viajante1(P,L,[P|Lcv],Pf,D):-menor_distancia_membro_lista(P,L,P1,L1,D1),caminho_caixeiro_viajante1(P1,L1,Lcv,Pf,D2),D is D1+D2.


menor_distancia_membro_lista(X,L,Ym,L1m,Dm):-findall(p(Y,L1,D),distancia_membro_lista(X,L,Y,L1,D),LYLD),menor_dml(LYLD,Ym,L1m,Dm).

distancia_membro_lista(X,L,Y,L1,D):-remove(Y,L,L1),((distancia(X,Y,D));distancia(Y,X,D)).

menor_dml([p(Y,L,D)],Y,L,D).
menor_dml([p(Y1,L1,D1)|LYLD],Ym,Lm,Dm):-menor_dml(LYLD,Y2,L2,D2),((D1<D2,!,Lm=L1,Ym=Y1,Dm is D1);(Lm=L2,Ym=Y2,Dm is D2)).



remove(X,[X|L],L).
remove(X,[Y|L],[Y|L1]):-remove(X,L,L1).


/*apaga(_,[ ],[ ]).
apaga(X,[X|L],M):-!,apaga(X,L,M).
apaga(X,[Y|L],[Y|M]):-apaga(X,L,M).*/


/* Selecionar um tourista */
selecciona_tour(IDtur,Lm,Ttotal):-tmp_disp_tur(IDtur,TT),roteiro_tmp_disp(IDtur,Tpoi,R),
					subconjunto(R,R1,Tpoi,Tpoi1),melhor_caminho(R1,Lm,D),elems(Lm,N),N<7,factor(Val),Tcaminho is D * Val,
					Ttotal is Tpoi1+Tcaminho,Ttotal=<TT,!.


selecciona_tour(IDtur,Lm,Ttotal):-tmp_disp_tur(IDtur,TT),roteiro_tmp_disp(IDtur,Tpoi,R),
					subconjunto(R,R1,Tpoi,Tpoi1),caminho_caixeiro_viajante(R1,Lm,D),factor(Val),Tcaminho is D * Val,
					Ttotal is Tpoi1+Tcaminho,Ttotal=<TT,!.

subconjunto([],[],T,T).
subconjunto([X|L],[X|L1],T,Tf):-subconjunto(L,L1,T,Tf).
subconjunto([Y|L],L1,T,Tf):-duracao(Y,TY), T1 is T-TY,subconjunto(L,L1,T1,Tf).
						
roteiro_tmp_disp(IDtur,T,R):-lista_poi_turista(IDtur,L),tmp_disp_tur(IDtur,X), poi_visitar(L,X,R,0,T).

poi_visitar([], _, [], ST, ST):-!.
poi_visitar([IDpoi|_], T, [], ST, ST):-duracao(IDpoi, TPoi), T<TPoi, !.
poi_visitar([IDpoi|LPoi], T, [IDpoi|LPoi1], STa, STf):-duracao(IDpoi, TPoi),T1 is T-TPoi, ST1 is STa+TPoi, poi_visitar(LPoi, T1, LPoi1, ST1, STf). 

elems([],0).
elems([H|T], X) :- elems(T, Y), X is Y + 1.


/* Execucao */
executa(IDtur):- selecciona_tour(IDtur,Lm,Ttotal), write(Lm), nl, traj_entre_poi(Lm).


traj_entre_poi([H|[]]).
traj_entre_poi([H,HS|T]):- hbf(H,HS,Perc,Total),
	nl, write(Perc), nl, append([HS],T,Poi_rest), 
	traj_entre_poi(Poi_rest).


/* A star */
hbf(Orig,Dest,Perc,Total):-
	estimativa(Orig,Dest,H),
	hbf1([c(H/0,[Orig])],Dest,P,Total),
	reverse(P,Perc).
							
hbf1(Percursos,Dest,Percurso,Total):-
	menor_percursoh(Percursos,Menor,Restantes),
	percursos_seguintesh(Menor,Dest,Restantes,Percurso,Total).
										
percursos_seguintesh(c(_/Dist,Percurso),Dest,_,Percurso,Dist):-
	Percurso=[Dest|_].

percursos_seguintesh(c(_,[Dest|_]),Dest,Restantes,Percurso,Total):-
	!, hbf1(Restantes,Dest,Percurso,Total).

percursos_seguintesh(c(_/Dist,[Ult|T]),Dest,Percursos,Percurso,Total):-
	findall(c(H1/D1,[Z,Ult|T]),proximo_noh(Ult,T,Z,Dist,Dest,H1/D1),Lista),
	append(Lista,Percursos,NovosPercursos),
	hbf1(NovosPercursos,Dest,Percurso,Total).
																		
menor_percursoh([Percurso|Percursos],Menor,[Percurso|Resto]):-
	menor_percursoh(Percursos,Menor,Resto),menorh(Menor,Percurso),!.

menor_percursoh([Percurso|Resto],Percurso,Resto).

menorh(c(H1/D1,_),c(H2/D2,_)):-C1 is H1+D1, C2 is H2+D2, C1<C2.

proximo_noh(X,T,Y,Dist,Dest,H/Dist1):-
	(seccao(X,Y,Z);seccao(Y,X,Z)),
	\+ member(Y,T),
	Dist1 is Dist + Z,
	estimativa(Y,Dest,H).

estimativa(C1,C2,Est):-
	coord_poi(C1,X1,Y1),
	coord_poi(C2,X2,Y2),
	DX is X1-X2,
	DY is Y1-Y2,
	Est is sqrt(DX*DX+DY*DY).

